package offer;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface NumDecodings {
    int numDecodings(String s);
}

class NumDecodingsImpl1 implements NumDecodings{
    static final String TEST_02 = "226";
    static final String TEST_01 = "12";
    public static void main(String[] args) {
        new NumDecodingsImpl1().numDecodings(TEST_02);
    }
    static final char[] MAPPING_TABLE = new char[]{'#','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    /**
     * consider back track method
     * @param s
     * @return
     */
    @Override
    public int numDecodings(String s) {
        return numDecodingHelper(s,0);
    }
    private boolean isValidMapping(String s){
        if(s.charAt(0) == '0'){
            return false;
        }else{
            if(Integer.valueOf(s)<=26){
                return true;
            }else{
                return false;
            }
        }
    }
    private int numDecodingHelper(String s,int sum){
        if("".equals(s) || s == null){
            return sum;
        }else{
            if(s.length() == 1){
                return sum ;
            }else{
                String s1 = s.substring(0,1);
                int sum1 = numDecodingHelper(s.substring(1,s.length()),sum);
                String s2 = s.substring(0,2);
                int sum2 = 0;
                if(isValidMapping(s2)){
                    sum2 = numDecodingHelper(s.substring(2),sum + 1);
                }
                return sum1 + sum2;
            }
        }
    }
}

class NumDecodingsImpl2 implements NumDecodings{

    /**
     *
     * @param s
     * @return
     */
    @Override
    public int numDecodings(String s) {
        Set<String> ans = new HashSet<>();
        Stack<Character> stack = new Stack<>();

        return 0;
    }
    private void numDecodingHelper(char[] strs,int current){

    }

}